﻿// 91. 最短Hamilton路径.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>

using namespace std;
/*
https://www.acwing.com/problem/content/93/
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 n。

接下来 n 行每行 n 个整数，其中第 i 行第 j 个整数表示点 i 到 j 的距离（记为 a[i,j]）。

对于任意的 x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式
输出一个整数，表示最短 Hamilton 路径的长度。

数据范围
1≤n≤20
0≤a[i,j]≤107
输入样例：
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例：
18
*/

const int N = 20;
int mm[N][N];
int n;
int dp[N][1 << N];

int dfs(int end, int state) {
	if (((state >> end) & 1) == 0) return 0x3f3f3f3f;
	if ((state & 1) == 0) return 0x3f3f3f3f;

	if (dp[end][state] != 0x3f3f3f3f) return dp[end][state];

	int& ret = dp[end][state];
	for (int i = 0; i < n; i++) {
		if (i != end)
			ret = min(ret, dfs(i, state & (~(1 << end))) + mm[i][end]);
	}

	return ret;
}

void solve1() {
	int l = 0; int r = n - 1;
	memset(dp, 0x3f, sizeof dp);
	dp[0][1] = 0;  //当前在0号点结尾 只经过state1的路径 经过的最小距离是0
	cout << dfs(n - 1, (1 << n) - 1);
}

void solve() {
	memset(dp, 0x3f, sizeof dp);
	dp[0][1] = 0;
	for (int m = 0; m < 1 << n; m++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if(i!=j&&  ((m >> i) & 1) != 0 && ((m >> j) & 1) != 0) {
					dp[i][m] = min(dp[i][m], dp[j][m & (~(1 << i))] + mm[j][i]);
				}
			}
		}
	}

	cout << dp[n - 1][ (1 << n) - 1];
}


int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mm[i][j];
		}
	}

	solve();

	return 0;
}
